Techniques related to virtual skywriting are discussed below. There have been proposals for allowing users of mobile devices to create and view virtual graffiti. Such proposals have taken an approach of allowing a user to create virtual graffiti and “pin” it to a particular real world object such as a wall, building, etc. However, this approach of virtual shared graffiti has certain limitations. Virtual graffiti may be accessible only to those in the vicinity of a virtual graffiti collection point. Also, there may be difficulties in recognizing, in an image, the object that graffiti is pinned to. In view of these shortcomings, embodiments described below relate to allowing users of mobile devices to create and view virtual skywriting.